ALGOL 60
来自维基百科，自由的百科全书
ALGOL 60（源自ALGOrithmic Language 1960的缩写），是在1960年创建的称为“算法语言”的一种编程语言。它是以后来称为ALGOL 58的“国际代数语言”为基础，其官方后继者是ALGOL 68，它们一起并称为ALGOL语言家族。Algol 60引进了许多新的概念如：块、词法作用域、递归[2]、巴科斯-诺尔范式（BNF），它在编程语言设计和发展演化中有着巨大的影响力。
历史
1960年，在巴黎举行的讨论会上，来自欧洲的诺尔、Bauer、Rutishauser、Samelson、范·韦恩加登、Vauquois、Woodger，与来自美国的佩利、巴科斯、麦卡锡、Katz、Wegstein和J. Green，共同发表了《算法语言ALGOL 60报告》[3]。戴克斯特拉实现了ALGOL 60语言的第一个编译器。在1962年罗马会议上，ALGOL 60报告得到了修订，并于1963年出版[4]。
ALGOL 60是程序设计语言发展史上的一个里程碑，影响到其后的Simula、CPL、ALGOL W、ISWIM、BCPL、B、Pascal、C、Scheme等。它标志着程序设计语言成为一门独立的科学学科，并为后来软件自动化及软件可靠性的发展奠定了基础。
ALGOL 60以及COBOL，是最初的企图标准化的编程语言。ALGOL60曾经提出两项ISO标准：
ALGOL 60在语言报告中没有I/O设施；诸多实现以少有相互兼容的方式定义了自己的设施。迄今ALGOL 60已经有了至少70个扩充、扩展、派生和子语言[7]。
| 名字 | 年份 | 作者 | 国家 | 描述 | 目标CPU |
|---|---|---|---|---|---|
| X1 ALGOL 60 | 1960年8月[8] | Edsger W. Dijkstra和Jaap A. Zonneveld |  荷兰 |
第一个ALGOL 60实现[9] | Electrologica X1 |
| ALGOL | 1960[10] | Edgar T. Irons |  美国 |
ALGOL 60 | CDC 1604 |
| Burroughs ALGOL（及一些变体） | 1961 | Burroughs公司（有Hoare、Dijkstra和其他人参与） | 美国 |
以Burroughs（后来基于Unisys MCP）计算机为基础。Burroughs方言包括了特殊系统编程方言比如ESPOL和NEWP。 | Burroughs大型系统和中型系统。 |
| Case ALGOL | 1961 | 美国 |
Simula最初签约为Case ALGOL的模拟器扩展 | UNIVAC 1107 | |
| GOGOL | 1961 | William M. McKeeman | 美国 |
用于ODIN分时系统 | PDP-1 |
| DASK ALGOL | 1961 | Peter Naur，Jørn Jensen |  丹麦 |
ALGOL 60 | Regnecentralen的DASK |
| SMIL ALGOL | 1962 | Torgil Ekman，Carl-Erik Fröberg |  瑞典 |
ALGOL 60 | 隆德大学的SMIL |
| GIER ALGOL | 1962 | Peter Naur，Jørn Jensen | 丹麦 |
ALGOL 60 | Regnecentralen的GIER |
| Dartmouth ALGOL 30[11] | 1962 | Thomas Eugene Kurtz，Stephen J. Garland，Robert F. Hargraves，Anthony W. Knapp，Jorge LLacer | 美国 |
ALGOL 60 | LGP-30 |
| Alcor Mainz 2002 | 1962 | Ursula Hill-Samelson，Hans Langmaack |  德国 |
Siemens 2002 | |
| ALCOR-ILLINOIS 7090 | 1962[12][13] | Manfred Paul，Hans Rüdiger Wiehle，David Gries，Rudolf Bayer | 美国， 西德
|
ALGOL 60，伊利诺伊大学和慕尼黑工业大学的实现，1962年-1964年 | IBM 7090 |
| USS 90 ALGOL | 1962 | L. Petrone |  意大利 |
||
| Elliott ALGOL | 1962 | C. A. R. Hoare |  英国 |
在他的1980年图灵奖演讲中讨论 | Elliott 803 & Elliott 503 |
| ALGOL 60 | 1962 | Roland Strobel[14] |  东德 |
由柏林德国科学院应用数学研究所实现 | Zeiss-Rechenautomat ZRA 1 |
| ALGOL 60 | 1962 | Bernard Vauquois，Louis Bolliet[15] |  法国
|
格勒诺布尔计算机科学与应用数学研究所(IMAG)和Bull机器公司 | Bull Gamma 60 |
| ALGOL Translator | 1962 | G. van der Mey，W.L. van der Poel | 荷兰 |
荷兰国家邮政局，电报电话 | ZEBRA |
| Kidsgrove ALGOL | 1963 | F. G. Duncan | 英国 |
英国电气公司KDF9 | |
| SCALP[16] | 1963 | Stephen J. Garland，Anthony W. Knapp，Thomas Eugene Kurtz | 美国 |
作为ALGOL 60子集的自齐备Algol处理器 | LGP-30 |
| VALGOL | 1963 | Val Schorre | 美国 |
META II编译器的编译器的测试品 | |
| FP6000 ALGOL | 1963 | Roger Moore |  加拿大 |
为Saskatchewan电力公司写作 | FP6000 |
| Whetstone | 1964[17] | Brian Randell，Lawford John Russell | 英国 |
英国电气公司原子能部。以Ferranti Pegasus为前提，国家物理实验室ACE和English Electric DEUCE实现。 | 英国电气公司KDF9 |
| ALGOL 60 | 1964 | Jean-Claude Boussard[18] | 法国 |
格勒诺布尔信息与数学应用研究所 | IBM 7090 |
| ALGOL-GENIUS | 1964 | Börje Langefors | 瑞典 |
增加受COBOL启发的数据记录和I/O | Datasaab D-21 |
| ALGOL 60 | 1965 | Claude Pair[19] | 法国 |
南锡科学学院计算中心 | IBM 1620 |
| Dartmouth ALGOL | 1965 | Stephen J. Garland，Sarr Blumson，Ron Martin | 美国 |
ALGOL 60 | 用于GE 235的Dartmouth分时系统 |
| NU ALGOL | 1965 |  挪威 |
UNIVAC | ||
| ALGOL 60 | 1965[20] | F.E.J. Kruseman Aretz | 荷兰 |
用于EL-X8的MC编译器 | Electrologica X8 |
| ALGEK | 1965 |  苏联 |
АЛГЭК，基于ALGOL-60并支持COBOL，用于经济任务 | Minsk-22 | |
| MALGOL | 1966 | publ. A. Viil，M Kotli，M. Rakhendi |  爱沙尼亚SSR |
Minsk-22 | |
| DJS-6 ALGOL | 1966 |  中国 |
华北计算所 | DJS-6 | |
| ALGAMS | 1967 | GAMS组织（ГАМС，中型机器自动化编程小组），协作于Comecon科学院 | 经济互助委员会 | Minsk-22，后来的ES EVM，BESM | |
| ALGOL/ZAM | 1967 |  波兰 |
波兰ZAM计算机 | ||
| DG/L | 1972 | 美国 |
DG Eclipse计算机家族 | ||
| NASE[21] | 1990 | Erik Schoenfelder | 德国 |
解释器 | Linux和MS Windows |
| MARST[22] | 2000 | Andrew Makhorin |  俄罗斯 |
ALGOL 60到C转换器 | GNU编译器套件支持的全部CPU；MARST是GNU计划成员 |
词法
| 优先级 | 运算符 | |
|---|---|---|
| 第一 算术 |
第一 | ↑（幂）
|
| 第二 | ×，/（实数），÷（整数）
| |
| 第三 | +，-
| |
| 第二 | <，≤，=，≥，>，≠
| |
| 第三 | ¬（非）
| |
| 第四 | ∧（与）
| |
| 第五 | ∨（或）
| |
| 第六 | ⊃（蕴涵）
| |
| 第七 | ≡（等价）
| |
和分界符:
,.⏨:;≔␣()[]‘’
在ISO 1672标准中，用:=表示≔（U+2254），用*表示×；用%表示÷，用**或^表示↑，用@表示科学记数法中指数运算的底数10所用符号⏨（U+23E8），用{表示‘，并且用}表示’，用空格 表示在字符串中的空白字符␣（U+2423）。
ALGOL 60有24个关键字：
|
|
|
|
|
|
还包括标准函数名字作为限制标识符：
|
|
|
|
|
|
|
|
|
关键字写法依赖于实现，常见的是一种叫做索绕（stropping）的方法，即将关键字大写并包围在两个'之间，例如将go to写为'GOTO'。在ISO 1672标准中关键字还包括对特定符号的某种文字转写：
| 符号 | 转写 | 符号 | 转写 | 符号 | 转写 | 符号 | 转写 | |||
|---|---|---|---|---|---|---|---|---|---|---|
[ |
'(/' | ] |
'/)' | ‘ |
'(' | ’ |
')' | |||
< |
'LT' | > |
'GT' | ≤ |
'LE' | ≥ |
'GE' | |||
= |
'EQ' | ≡ |
'EQV' | ≠ |
'NE' | ¬ |
'NOT' | |||
∧ |
'AND' | ∨ |
'OR' | ⊃ |
'IMPL' | ÷ |
'/' |
语义
在ALGOL 60中，“复合语句”被定义为：包围在语句括号begin和end之间的成序列的语句，形成一个复合语句。块被定义为：成序列的声明，跟随着成序列的语句，并被包围在begin和end之间，形成一个块；所有声明以这种方式出现在一个块中，并只在这个块中有效。[23]
一个程序是特定的一个块或复合语句，它不包含在另一个语句之中，并且不使用不包含在它之中的其他语句。在1976年的修改版语言报告中，程序只能包含在叫做“环境块”的假定总是存在的一个虚构块之中，除了可以使用在环境块中声明的过程标识符和函数指定符之外，不使用不包含在它之中的其他语句。
量（quantity）被区分出如下种类：简单变量、数组、标签、switch（switch列表由标签组成[24]）和过程。声明负担定义在程序中用到的量的特定属性，并给它们关联上标识符。声明包括：类型声明、数组声明、switch声明和过程声明。量的作用域是语句和表达式的集合，在其中关联于这个量的标识符的声明是有效的。所有的块，自动地介入名称目录（nomenclature）的一个新的层级：
- 在这个块内出现的标识符，可以通过合适的声明，而被指定为局部于所论及的这个块。这个标识符在这个块里面的所表示的实体，不存在于它的外面。这个标识符在这个块外面的所表示的任何实体，在这个块里面是不可见的。
- 除了表示标签的标识符之外，一个标识符，如果出现在一个块中，而且并非声明于这个块中，则它非局部于这个块[25]，就是说它在这个块里面和在紧邻其外的层级中所表示的是同一个实体。
- 因为块中的语句自身可以是一个块，局部和非局部于一个块的概念，必须递归地去理解，就是说非局部于一个块
A的一个标识符，可是亦可否地，非局部于A是其中语句的块B。
这动态的蕴涵了：在通过begin进入一个块的时候，所有为这个块声明的标识符，假定了这个给定声明的本性所蕴涵的意义（significance）；如果这些标识符已经被外面的其他声明所定义，这时它们被给予新的意义；在另一方面，并非为这个块声明的标识符，保持它们旧有的含义。在通过end或go to语句退出一个块的时候，为这个块声明的标识符失去它们的局部意义。声明可以标记上额外的声明符own，其效果为：在重新进入一个块的时候，自有的这些量的值将不变更而仍是上次退出时的值，然而声明的没有标记上own的变量的值是未定义的。
在描述算法处理的程序中，主要构成者是算术表达式、布尔表达式，和得到语句标签的指定（designational）表达式。除了特定的分界符之外，表达式的构成者包括：逻辑值、数值、变量、函数指定式，和基本的算术、关系、逻辑运算符（operator）及顺序运算符。用以形成语句的关键字，在ALGOL 60中被归入顺序运算符和分隔符之中。
变量是对一个单一值的指名（designation）。下标（subscripted）变量指定（designate）多维数组的元素的值，这里将数组元素称为“组成元件”（component）[26]。函数指定式（designator）定义单一的数量值或逻辑值，它们是将给定的由过程声明定义的规则集合，应用于固定的实际参数集合的结果。
现在通常将变量定义为抽象的存储位置，它含有了被称为一个值的某种已知或未知的信息量，并且配对了关联的符号名字。在ALGOL 60中，某些语法单位，比如表达式及其构成者和数组标识符，被称为拥有值。各种“类型”即integer、real和Boolean，指称（denote）值的基本的属性。
在左圆括号和匹配的右圆括号之间的表达式（parenthesized expression）自行求值，而这个值被用于后续的计算之中；因此通过适当的圆括号放置，总是可以在表达式之内安排出想要的运算次序。
ALGOL 60将语句分为三类：无条件语句、条件语句和for语句。赋值语句担负将表达式的值，指派（assign）到一个或多个变量，或者在定义函数指定式的值的过程主体中指派到过程标识符；在作为指派目标的下标变量中出现的任何下标表达式，先于得出所指派之值的表达式，而按从左至右顺序求值。空无的虚设（dummy）语句不执行任何运算。过程语句负担实施调用一个过程主体的执行。
控制流程语句包括：go to跳转语句、条件语句、for循环语句。go to语句结合了无条件go to和计算go to二者，goto语句不能从块外跳转到块内的标签，但可以跳转进入复合语句。条件语句包括if语句（即if <布尔表达式> then <无条件语句>），和if语句经由关键字else与随后的语句联合在一起的形式（即<if语句> else <语句>）。ALGOL 60在if语句和for语句中介入了子句概念，算术表达式、布尔表达式和指定表达式，可以是条件表达式（即if ~ then ~ else ~）[27]。
由于变量和函数指定式二者的语法定义都包含表达式，表达式及其构成者的定义必须是递归的。由于成序列的语句，可以被组织成复合语句和块，语句的定义必需是递归的。ALGOL 60采用了左递归的巴科斯范式（BNF）。
在ALGOL 60中，过程声明担负定义过程标识符所关联的过程，其主要构成者是过程主体，它是一个语句或一段代码。过程主体总是表现得如同一个块，不管它是否有着块的形式；故而标记了在过程主体内语句或者主体自身的标签的作用域，永远不能延伸超出这个过程主体[28]。
过程主体关联着一个头部，它规定了出现在过程主体内的代表形式参数的特定标识符。过程的参数传递有两种求值策略：传名调用和传值调用。在过程声明中，通过对形式参数名字前导value来指定传值调用，缺省为传名调用。在过程主体是用ALGOL语言写的语句的情况下，过程语句执行它的效果，等价于在程序上进行下列操作的效果：
- 声明为传值调用的形式参数，都要被赋值即指派上对应的实际参数的值，这些指派被认为是在进入过程主体之前显式进行的。其效果如同创建了包围着这个过程主体的一个额外的块，在其中所做的这些指派针对的是局部于这个虚构块的变量，它们具有在相应规定中给出的类型。作为结论，传值调用的变量，被认为非局部于过程主体，但是局部于这个虚构块。
- 声明为传名调用的形式参数，在整个过程主体内，要被替代为对应的实际参数，并且只要语法上可能就对这些实际参数包围上圆括号。在通过这个名字替代处理而插入的标识符，和已经存在于过程主体之内的其他标识符，二者之间的可能冲突，将凭借对涉及到的（这个过程主体的）形式标识符或局部标识符的适合的系统性变更来避免[29]。
- 最终经过上述修改后的过程主体，被插入到过程语句的位置上并被执行。如果调用这个过程的位置，处在这个过程主体的任何非局部量[30]的作用域的外面，在通过这个过程主体替代处理而插入的标识符，和在这个过程语句或函数指定式所在位置上其声明有效的标识符，二者之间的可能冲突，将通过（在发起调用的这个层级上）对后者标识符的适合的系统性变更来避免[31]。
对于定义函数指定式的值的过程声明，在其过程主体中，必须出现具有过程标识符在其左侧部分中的一个或多个赋值语句，其中至少有一个必须被执行；并且这个过程标识符所关联的类型，必须通过以类型声明符作为其过程声明的最先符号的样貌来声明。最后那个这样指派的值，被用来继续此函数指定式在其中出现的表达式的求值。在这个过程主体中，这个过程标识符的不在赋值语句左侧部分中的任何出现，指示了这个过程的激活（activation）。
两个传名调用形式参数，其对应的实际参数之间可能存在依赖关系，比如第一个是整数变量i，而第二个是下标变量A[i]，从而导致后者形式参数也依赖于前者形式参数，利用传名调用和这种副作用可以实现Jensen设备[32]；它典型的用于定义对应于的级数过程Sum(k, l, u, ak)，它有两个传名调用的形式参数：索引变量k和通项（general）表达式ak。
对于交换两个参数的值的swap(x, y)过程，其过程主体定义为：t:=x; x:=y; y:=t，这种依赖性副作用会导致可能出现异常行为，由于名字替代机制相当于宏展开（expansion），过程语句swap(i, A[i])中下标变量A[i]的下标i未经求值，对应的过程主体就转换成为：t:=i; i:=A[i]; A[i]:=t。1964年IFIP工作组2.1制定了《SUBSET ALGOL 60报告》，在这个子集语言中对“完全的名字概念”（full name-concept）增加了一项限制：在名字替代（传名调用）中，实际参数只能是一个标识符或字符串。
在过程的参数列表( … <参数分界符> … )中，有可选的“) <字母串>: (”样式的参数分界符[33]。众所周知的传名调用实现采用了thunk[a][35]。Donald Knuth设计了“男人抑或男孩测试”，来区分编译器是否正确的实现了“递归和非局部引用”，这个测试用到了传名调用。
例子
下面是语言报告中过程声明的一个例子[b]：
procedure Absmax(a) Size:(n, m) Result:(y) Subscripts:(i, k);
value n, m; array a; integer n, m, i, k; real y;
comment 矩阵a，其大小为n乘m，其绝对值最大的
元素被传送到y，并且这个元素的下标是i和k。 ;
begin
integer p, q;
y := 0; i := k := 1;
for p := 1 step 1 until n do
for q := 1 step 1 until m do
if abs(a[p, q]) > y then
begin
y := abs(a[p, q]);
i := p; k := q
end
end Absmax
在1976年修改版语言报告的环境块中，定义了输入输出过程：inchar、outchar、length、outstring、outterminator、ininteger、outinteger、inreal和outreal，下面以其中的outinteger作为演示例子：
procedure outinteger(channel, int);
value channel, int;
integer channel, int;
comment 将表示int的值的那些字符，
加上尾随的终结符传递到channel。 ;
begin
procedure digits(int);
value int; integer int;
begin
integer j;
comment 使用递归从右至左求值数字，
但从左至右打印它们。 ;
j := int ÷ 10;
int := int - 10 × j;
if j ≠ 0 then
digits(j);
outchar(channel, ‘0123456789’, int + 1)
end digits;
if int < 0 then
begin
outchar(channel, ‘-’, 1);
int := -int
end;
digits(int); outterminator(channel)
end outinteger
这里调用到的outchar(channel, str, int)，将在字符串str中对应整数int的值的那个字符，传递到通道channel；outterminator(channel)，用于输出在数值之后的终结符（即空格、换行或分号）。此外，IFIP工作组2.1在1964年曾制定《ALGOL 60输入输出过程报告》，其中定义了insymbol、outsymbol、length、inreal、outreal、inarray和outarray，这里的多维数组采用了横行为主（Row major）次序[36]。
参见
注释与引用
外部链接
Wikiwand - on
Seamless Wikipedia browsing. On steroids.